package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
 * //
 * // 示例:
 * //
 * // 输入: 3
 * //输出: 5
 * //解释:
 * //给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
 * //
 * //   1         3     3      2      1
 * //    \       /     /      / \      \
 * //     3     2     1      1   3      2
 * //    /     /       \                 \
 * //   2     1         2                 3
 * // Related Topics 树 动态规划
 * // 👍 879 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-04 07:44:20
 */
public class UniqueBinarySearchTrees {
    public static void main(String[] args) {
        Solution solution = new UniqueBinarySearchTrees().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numTrees(int n) {
            int[] g = new int[n+1];
            g[0] = 1;
            g[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    g[i] += g[j - 1] * g[i - j];
                }
            }
            return g[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}